package leetcode.editor.week.week307;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 2385. 感染二叉树需要的总时间
// https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/
public class Solution2385 {

    // dfs 不建图
    /*public int amountOfTime(TreeNode root, int start) {
        dfs(root, 0, start);
        return ans;
    }

    int ans = 0;    // 用时最短
    int depth = -1; // 起始节点的高度

    public int dfs(TreeNode root, int level, int start) {
        if (root == null) return 0;

        if (root.val == start) depth = level;

        int left = dfs(root.left, level + 1, start);

        boolean inLeft = depth != -1;

        int right = dfs(root.right, level + 1, start);

        if (root.val == start) ans = Math.max(Math.max(left, right), ans);

        if (inLeft) ans = Math.max(depth - level + right, ans);
        else ans = Math.max(depth - level + left, ans);

        return Math.max(left, right) + 1;
    }*/

    List<List<Integer>> graph;
    int max = 0;    // 记录最大数字，创建visited的时候节约内存

    // DFS建图、BFS搜索最长路径
    // https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/solution/by-nicolas-2-l379/
    public int amountOfTime(TreeNode root, int start) {
        // 1 <= Node.val <= 105
        // 初始化图的大小
        int N = 100001;
        this.graph = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            graph.add(new LinkedList<>());
        }

        buildGraph(root);
        return bfs(start);
    }

    // 建图
    public void buildGraph(TreeNode root) {
        max = Math.max(root.val, max);
        if (root.left != null) {
            graph.get(root.val).add(root.left.val);
            graph.get(root.left.val).add(root.val);
            buildGraph(root.left);
        }

        if (root.right != null) {
            graph.get(root.val).add(root.right.val);
            graph.get(root.right.val).add(root.val);
            buildGraph(root.right);
        }
    }

    // BFS求最大路径
    public int bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        int level = 0, res = 0;
        boolean[] visited = new boolean[max + 1];
        visited[start] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int next : graph.get(cur)) {
                    if (visited[next]) continue;
                    queue.offer(next);
                    visited[next] = true;
                }
            }
            level++;
        }

        return level - 1;
    }

}
